package org.example.myleet.p1414;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int findMinFibonacciNumbers(int k) {
        List<Integer> fibonacciList = getFibonacciNumbers(k);
        int count = 0;
        int end = fibonacciList.size() - 1;
        while (k > 0) {
            int i = findTargetInFibonacciList(fibonacciList, k, 0, end);
            end = i;
            int f = fibonacciList.get(i);
            k -= f;
            ++count;
        }
        return count;
    }

    private List<Integer> getFibonacciNumbers(int target) {
        List<Integer> fibonacciList = new ArrayList<>(46);
        int f1 = 1;
        fibonacciList.add(f1);
        int f2 = 1;
        fibonacciList.add(f2);
        int f;
        while (f2 < target) {
            f = f1;
            f1 = f2;
            f2 = f + f1;
            fibonacciList.add(f2);
        }
        return fibonacciList;
    }

    private int findTargetInFibonacciList(List<Integer> fibonacciList, int target, int from, int to) {
        while (from < to) {
            int m = (from + to + 1) >> 1;
            int f = fibonacciList.get(m);
            if (f == target) {
                return m;
            } else if (target < f) {
                to = m - 1;
            } else {
                from = m;
            }
        }
        return from;
    }
}
